1. Industrial Fields of Application
This invention relates to the implementation of a variable length coder (also known as "huffman Coder", or "entropy coder") and bitstream formatter for use in digital video coders.
2. Related Art of the Invention
In digital video coding, a video signal is compressed and transmitted as a bitstream conforming to a specific syntax like that of H.261 (described by CCITT Subgroup XV Document, "Recommendation H.261-Video Codec for Audiovisual Services at px 64 kbit/s", International Telegraph and Telephone Consultative committee, Study Group XV-Report R 37, August 1990), MPEG-1 (ISO MPEG Document, "CD 11172-Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbps", International Organization for Standardization, ISOIEC/JTC1/SC2/WG8, 1992), or MPEG-2 (ISO MPEG Document, "Third Working Draft (New York) Ammended by the Ad Hoc Group on WD Editing", International Organization for Standardization, ISO/IEC, Aug. 27, 1993). In these coders a lossy coding algorithm based on the discrete cosine transform (DCT) precedes a lossless encoder based on variable length coding which also performs bitstream syntax formatting. The input to the lossless coder (also know as "Variable Length Coder" or VLC) typically consists of transform coefficients for a macroblock of video data (16.times.16 for MPEG-1). the side information for the macroblock (macroblock type, motion vectors, etc. for MPEG-1), and the header side information corresponding to slices, pictures, or even more granular divisions of coded video data.
One function of the VLC is to convert the fixed length input data to variable length data. For example, this can hew done by run-level coding AC transform coefficients and entropy encoding the combinations of run-levels. It may also entropy encode some of the side information. Another function of the VLC is to format (reorder) the data to conform to the output bitstream syntax. A third function of the VLC is to determine rate control feedback parameters which are used to maintain the output bitrate near a target bitrate by controlling the amount of quantization imposed on DCT coefficients.
Most existing lossless coders support a subset of the existing standards, with no possibility to change the bitstream syntax. An example of such a device is the LSI LOGIC L64750 (described by LSI Logic Integrated Circuit Data Sheet, "L64750/51 CCITT Variable Length Coder/Decoder", Order Number 44023, April 1991) which supports the H.261 bitstream syntax only. Morrison (see "Video Coder", Morrison, et al, U.S. Pat. No. 4,985,766, Jan. 15, 1991) formats the bitstream by buffering coefficient data and side information separately. Special data switches are written in each buffer to indicate when the reading of one buffer should be toggled to the other buffer. By doing so, the data can be read from the buffers in the order necessary for the desired bitstream syntax. The reordered data is stored in a rate control buffer, and is read out and variable length coded at a rate necessary to result in the desired bitstream bitrate. The rate control feedback parameter in this case is the fullness of the rate control buffer. The number of bits of bitstream data read from the buffer is subtracted from the number of bits written into the buffer to result in a measure of the buffer's fullness. The buffer's fullness is used to moderate the amount of coefficient quantization so that the buffer does not underflow or overflow.
There are several problems which this invention solves. Due to the rapidly changing digital A/V coding technology and also due to the wide range of applications, it is necessary to support various bitstream syntaxes and allow for new syntax in the future. Formatting the data is typically very complicated, and is dependent upon the bitstream syntax, coding algorithm, and the characteristics of the coded data. An object of this invention is to develop a VLC in which changes to the syntax have no affect on the logic design of the coder. This is necessary especially for hardware which will support future standards now under development such as MPEG-2 or ATV in the USA.
A second problem solved by this invention is the need for a VLC small enough in size for implementation in VLSI suitable for a commercial consumer product. A third problem solved by this invention is that the VLC must be simple to use in order to make the development of consumer video coders easy and economical. An object of this invention is to support a simple interface to the VLC circuit. A fourth problem solved by this invention is that the data throughput is very high. For 4:1:1 sampled wide TV, a macroblock must be coded every 15 microseconds. The fixed length data (quantized coefficients plus side information) input rate to the VLC exceeds 27 MHz in this case. An object of this invention is to support the very high data throughput and simultaneously allow the VLC to format the macroblocks in a programmable fashion.